/*
 * @lc app=leetcode id=483 lang=cpp
 *
 * [483] Smallest Good Base
 */

// @lc code=start
class Solution {
public:
    string smallestGoodBase(string n) {
        long long num = stoll(n);
        for(long long m=1+log2(num); m>=1; m--){		//为了k最小，我们应该找大m
            long long l=2,r=powl(num,1.0/m)+1,mid;
            while(l <= r){		
                mid = (l+r)/2;
                long long sum=1;
                for(long long i=0; i<m && sum<=num; i++){
                    sum = sum*mid + 1;
                }
                if(sum == num)  return to_string(mid);
                else if(sum > num)  r = mid-1;
                else    l = mid+1;
            }
        }
        return "";
    }
};
// @lc code=end

